package 算法基础模板.chapter_01.双指针.sliding_window;

/**
 * 395. 至少有K个重复字符的最长子串
 * 找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
 *
 * 示例 1:
 *
 * 输入:
 * s = "aaabb", k = 3
 *
 * 输出:
 * 3
 *
 * 最长子串为 "aaa" ，其中 'a' 重复了 3 次。
 * 示例 2:
 *
 * 输入:
 * s = "ababbc", k = 2
 *
 * 输出:
 * 5
 *
 * 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
 * @author Summerday
 */
public class LC395 {

    public int longestSubstring(String s, int k) {
        int ans = 0;
        int n = s.length();
        char[] chs = s.toCharArray();
        // //每个循环中，滑动窗口内只能有i个不同字符
        for(int i = 1; i <= 26; i ++){
            // 记录每个字符出现的次数  'a' 97 'z' 122
            int[] cnt = new int[123];
            int l = 0, r = 0;
            // fre : 字符种类数
            // knum : 大于等于k的字符数
            int fre = 0, knum = 0;
            while(r < n){
                cnt[chs[r]] ++;
                if(cnt[chs[r]] == 1) fre ++;
                if(cnt[chs[r]] == k) knum ++;
                while(l < r && fre > i){
                    if(cnt[chs[l]] == k) knum --;
                    if(cnt[chs[l]] == 1) fre --;
                    cnt[chs[l]] --;
                    l ++;
                }
                //窗口内出现i个不同字符并且每个字符都大于等于k
                if(fre == i && knum == fre){
                    ans = Math.max(ans, r - l + 1);
                }
                r ++;
            }
        }
        return ans;
    }
}
